// 版权所有2011 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package syntax

import (
	"sort"
	"strings"
	"unicode"
	"unicode/utf8"
)

// 错误描述了解析正则表达式失败，并给出了错误的表达式。
type Error struct {
	Code ErrorCode
	Expr string
}

func (e *Error) Error() string {
	return "error parsing regexp: " + e.Code.String() + ": `" + e.Expr + "`"
}

// 错误代码描述了解析正则表达式的失败。
type ErrorCode string

const (
	// 意外错误
	ErrInternalError ErrorCode = "regexp/syntax: internal error"

	// 解析错误
	ErrInvalidCharClass      ErrorCode = "invalid character class"
	ErrInvalidCharRange      ErrorCode = "invalid character class range"
	ErrInvalidEscape         ErrorCode = "invalid escape sequence"
	ErrInvalidNamedCapture   ErrorCode = "invalid named capture"
	ErrInvalidPerlOp         ErrorCode = "invalid or unsupported Perl syntax"
	ErrInvalidRepeatOp       ErrorCode = "invalid nested repetition operator"
	ErrInvalidRepeatSize     ErrorCode = "invalid repeat count"
	ErrInvalidUTF8           ErrorCode = "invalid UTF-8"
	ErrMissingBracket        ErrorCode = "missing closing ]"
	ErrMissingParen          ErrorCode = "missing closing )"
	ErrMissingRepeatArgument ErrorCode = "missing argument to repetition operator"
	ErrTrailingBackslash     ErrorCode = "trailing backslash at end of expression"
	ErrUnexpectedParen       ErrorCode = "unexpected )"
)

func (e ErrorCode) String() string {
	return string(e)
}

// 标志控制解析器的行为并记录有关regexp上下文的信息。
type Flags uint16

const (
	FoldCase      Flags = 1 << iota // 不区分大小写的匹配
	Literal                         // 将模式视为文字字符串
	ClassNL                         // 允许[^a-z]和[[：space:]等字符类匹配换行符
	DotNL                           // 允许。要匹配换行符
	OneLine                         // 将^和$视为文本开头和结尾的唯一匹配
	NonGreedy                       // 将重复运算符默认为非贪婪
	PerlX                           // 允许Perl扩展
	UnicodeGroups                   // 允许\p{Han}、\p{Han}用于Unicode组和否定
	WasDollar                       // regexp OpEndText是$，not\z 
	Simple                          // regexp不包含计数重复

	MatchNL = ClassNL | DotNL

	Perl        = ClassNL | OneLine | PerlX | UnicodeGroups // 尽可能接近Perl 
	POSIX Flags = 0                                         // POSIX语法
)

// 解析堆栈的伪操作。
const (
	opLeftParen = opPseudo + iota
	opVerticalBar
)

// maxHeight是regexp解析树的最大高度。
// 这有点随意选择，但其想法是足够大，没有人会在实际使用中真正命中，但同时足够小，Regexp树上的递归不会达到1GB Go堆栈限制。
// 单个递归帧的最大堆栈量可能是
// 接近1kB，因此这可能会被提高，但似乎不太可能
// 人们将regexp嵌套得如此之深。ABCFDG 
// 使用深度1000应该有足够的余量。
// 作为一种优化，我们甚至不需要计算高度
// 直到我们至少分配了maxHeight Regexp结构。
const maxHeight = 1000

type parser struct {
	flags       Flags     // 解析模式标志
	stack       []*Regexp // 解析表达式堆栈
	free        *Regexp
	numCap      int // 看到的捕获组数
	wholeRegexp string
	tmpClass    []rune          // 临时字符类工作空间
	numRegexp   int             // 分配的正则表达式数
	height      map[*Regexp]int // 高度限制检查的正则表达式高度
}

func (p *parser) newRegexp(op Op) *Regexp {
	re := p.free
	if re != nil {
		p.free = re.Sub0[0]
		*re = Regexp{}
	} else {
		re = new(Regexp)
		p.numRegexp++
	}
	re.Op = op
	return re
}

func (p *parser) reuse(re *Regexp) {
	if p.height != nil {
		delete(p.height, re)
	}
	re.Sub0[0] = p.free
	p.free = re
}

func (p *parser) checkHeight(re *Regexp) {
	if p.numRegexp < maxHeight {
		return
	}
	if p.height == nil {
		p.height = make(map[*Regexp]int)
		for _, re := range p.stack {
			p.checkHeight(re)
		}
	}
	if p.calcHeight(re, true) > maxHeight {
		panic(ErrInternalError)
	}
}

func (p *parser) calcHeight(re *Regexp, force bool) int {
	if !force {
		if h, ok := p.height[re]; ok {
			return h
		}
	}
	h := 1
	for _, sub := range re.Sub {
		hsub := p.calcHeight(sub, false)
		if h < 1+hsub {
			h = 1 + hsub
		}
	}
	p.height[re] = h
	return h
}

// 解析堆栈操作。

// push将regexp-re推送到解析堆栈上并返回regexp。
func (p *parser) push(re *Regexp) *Regexp {
	if re.Op == OpCharClass && len(re.Rune) == 2 && re.Rune[0] == re.Rune[1] {
		// 单个符文。
		if p.maybeConcat(re.Rune[0], p.flags&^FoldCase) {
			return nil
		}
		re.Op = OpLiteral
		re.Rune = re.Rune[:1]
		re.Flags = p.flags &^ FoldCase
	} else if re.Op == OpCharClass && len(re.Rune) == 4 &&
		re.Rune[0] == re.Rune[1] && re.Rune[2] == re.Rune[3] &&
		unicode.SimpleFold(re.Rune[0]) == re.Rune[2] &&
		unicode.SimpleFold(re.Rune[2]) == re.Rune[0] ||
		re.Op == OpCharClass && len(re.Rune) == 2 &&
			re.Rune[0]+1 == re.Rune[1] &&
			unicode.SimpleFold(re.Rune[0]) == re.Rune[1] &&
			unicode.SimpleFold(re.Rune[1]) == re.Rune[0] {
		// 不区分大小写的符文，如[Aa]或[Δδ]。
		if p.maybeConcat(re.Rune[0], p.flags|FoldCase) {
			return nil
		}

		// 重写为（不区分大小写）文本。
		re.Op = OpLiteral
		re.Rune = re.Rune[:1]
		re.Flags = p.flags | FoldCase
	} else {
		// 增量连接。
		p.maybeConcat(-1, 0)
	}

	p.stack = append(p.stack, re)
	p.checkHeight(re)
	return re
}

// maybeConcat实现了文本符文到字符串节点的增量连接。在每次推送之前，解析器都会调用这个
// ，因此只有堆栈的顶部片段
// 可能需要处理。因为这是在推之前调用的，所以
// 最上面的文字不再受像*
// （否则ab*将变成（ab）*）这样的运算符的约束。）
// 如果r>=0，剩下一个节点，可能是因为Concat使用它
// 用给定的标志来推送r。
// maybeConcat报告r是否被推送。
func (p *parser) maybeConcat(r rune, flags Flags) bool {
	n := len(p.stack)
	if n < 2 {
		return false
	}

	re1 := p.stack[n-1]
	re2 := p.stack[n-2]
	if re1.Op != OpLiteral || re2.Op != OpLiteral || re1.Flags&FoldCase != re2.Flags&FoldCase {
		return false
	}

	// 将re1推入re2。
	re2.Rune = append(re2.Rune, re1.Rune...)

	// 如有可能，重复使用re1。
	if r >= 0 {
		re1.Rune = re1.Rune0[:1]
		re1.Rune[0] = r
		re1.Flags = flags
		return true
	}

	p.stack = p.stack[:n-1]
	p.reuse(re1)
	return false // 未推送r 
}

// 文字推送堆栈上符文r的文字regexp。
func (p *parser) literal(r rune) {
	re := p.newRegexp(OpLiteral)
	re.Flags = p.flags
	if p.flags&FoldCase != 0 {
		r = minFoldRune(r)
	}
	re.Rune0[0] = r
	re.Rune = re.Rune0[:1]
	p.push(re)
}

// minFoldRune返回与r相等的最小符文折叠。
func minFoldRune(r rune) rune {
	if r < minFold || r > maxFold {
		return r
	}
	min := r
	r0 := r
	for r = unicode.SimpleFold(r); r != r0; r = unicode.SimpleFold(r) {
		if min > r {
			min = r
		}
	}
	return min
}

// op将具有给定op的regexp推送到堆栈
// 并返回该regexp。
func (p *parser) op(op Op) *Regexp {
	re := p.newRegexp(op)
	re.Flags = p.flags
	return p.push(re)
}

// repeat根据op、min、max将顶层堆栈元素替换为重复的元素。
// before是从repeation运算符开始的regexp后缀。
// after是重复运算符后面的regexp后缀。
// repeat返回更新后的“after”和错误（如果有）。
func (p *parser) repeat(op Op, min, max int, before, after, lastRepeat string) (string, error) {
	flags := p.flags
	if p.flags&PerlX != 0 {
		if len(after) > 0 && after[0] == '?' {
			after = after[1:]
			flags ^= NonGreedy
		}
		if lastRepeat != "" {
			// 在Perl中，不允许堆叠重复运算符：
			// a**是一个语法错误，不是双星，a++表示
			// 完全其他的东西，我们不支持！
			return "", &Error{ErrInvalidRepeatOp, lastRepeat[:len(lastRepeat)-len(after)]}
		}
	}
	n := len(p.stack)
	if n == 0 {
		return "", &Error{ErrMissingRepeatArgument, before[:len(before)-len(after)]}
	}
	sub := p.stack[n-1]
	if sub.Op >= opPseudo {
		return "", &Error{ErrMissingRepeatArgument, before[:len(before)-len(after)]}
	}

	re := p.newRegexp(op)
	re.Min = min
	re.Max = max
	re.Flags = flags
	re.Sub = re.Sub0[:1]
	re.Sub[0] = sub
	p.stack[n-1] = re
	p.checkHeight(re)

	if op == OpRepeat && (min >= 2 || max >= 2) && !repeatIsValid(re, 1000) {
		return "", &Error{ErrInvalidRepeatSize, before[:len(before)-len(after)]}
	}

	return after, nil
}

// repeatIsValid报告重复是否有效。
// 有效意味着顶级重复
// 和任何内部重复的组合不超过
// 最内层内容的n个副本。
// 此函数重新遍历regexp树，并为每次重复调用，因此我们必须担心在解析器中产生二次行为。
// 我们只在min或max>=2时调用repeatIsValid来避免这种情况。
// 在这种情况下，任何>=2嵌套的深度只能达到9，而不会触发解析错误，因此每个子树只能重新遍历9次。
func repeatIsValid(re *Regexp, n int) bool {
	if re.Op == OpRepeat {
		m := re.Max
		if m == 0 {
			return true
		}
		if m < 0 {
			m = re.Min
		}
		if m > n {
			return false
		}
		if m > 0 {
			n /= m
		}
	}
	for _, sub := range re.Sub {
		if !repeatIsValid(sub, n) {
			return false
		}
	}
	return true
}

// concat将堆栈顶部（最顶部的“|”或“（”）上方）替换为其串联。
func (p *parser) concat() *Regexp {
	p.maybeConcat(-1, 0)

	// 向下扫描以查找伪运算符|或（.
	i := len(p.stack)
	for i > 0 && p.stack[i-1].Op < opPseudo {
		i--
	}
	subs := p.stack[i:]
	p.stack = p.stack[:i]

	// 空连接是特例。
	if len(subs) == 0 {
		return p.push(p.newRegexp(OpEmptyMatch))
	}

	return p.push(p.collapse(subs, OpConcat))
}

// alternate用其alternate替换堆栈顶部（最顶部的“（”）上方）。
func (p *parser) alternate() *Regexp {
	// 向下扫描以查找伪运算符（.
	// 上面没有|运算符（.
	i := len(p.stack)
	for i > 0 && p.stack[i-1].Op < opPseudo {
		i--
	}
	subs := p.stack[i:]
	p.stack = p.stack[:i]

	// 确保顶级类是干净的。
	// 所有其他类都已经是干净的（请参见swapVerticalBar）。
	if len(subs) > 0 {
		cleanAlt(subs[len(subs)-1])
	}

	// 空替代是特殊情况
	// （不应发生，但易于处理）。
	if len(subs) == 0 {
		return p.push(p.newRegexp(OpNoMatch))
	}

	return p.push(p.collapse(subs, OpAlternate))
}

// cleanAlt清洗re，以便最终包含在替代品中。
func cleanAlt(re *Regexp) {
	switch re.Op {
	case OpCharClass:
		re.Rune = cleanClass(&re.Rune)
		if len(re.Rune) == 2 && re.Rune[0] == 0 && re.Rune[1] == unicode.MaxRune {
			re.Rune = nil
			re.Op = OpAnyChar
			return
		}
		if len(re.Rune) == 4 && re.Rune[0] == 0 && re.Rune[1] == '\n'-1 && re.Rune[2] == '\n'+1 && re.Rune[3] == unicode.MaxRune {
			re.Rune = nil
			re.Op = OpAnyCharNotNL
			return
		}
		if cap(re.Rune)-len(re.Rune) > 100 {
			// re。符文不会再长了。
			// 复制或内联以回收存储。
			re.Rune = append(re.Rune0[:0], re.Rune...)
		}
	}
}

// collapse返回将op应用于sub的结果。
// 如果sub包含op节点，它们都会被提升
// 这样就永远不会有concat的concat或
// alternate的alternate。
func (p *parser) collapse(subs []*Regexp, op Op) *Regexp {
	if len(subs) == 1 {
		return subs[0]
	}
	re := p.newRegexp(op)
	re.Sub = re.Sub0[:0]
	for _, sub := range subs {
		if sub.Op == op {
			re.Sub = append(re.Sub, sub.Sub...)
			p.reuse(sub)
		} else {
			re.Sub = append(re.Sub, sub)
		}
	}
	if op == OpAlternate {
		re.Sub = p.factor(re.Sub)
		if len(re.Sub) == 1 {
			old := re
			re = re.Sub[0]
			p.reuse(old)
		}
	}
	return re
}

// 从替换列表子目录中选择常用前缀。
// 它返回一个替换列表，该替换列表重用相同的存储，并且
// 释放（传递给p.reuse）任何删除的*regexp。例如，
// ABC | ABD | AEF | BCX | BCY 
// 通过文字前缀提取简化为
// A（B（C | D | EF）| BC BC（X | Y）
// 通过字符类引入
// A（B[CD]| EF。
func (p *parser) factor(sub []*Regexp) []*Regexp {
	if len(sub) < 2 {
		return sub
	}

	var str []rune
	var strflags Flags
	start := 0
	out := sub[:0]
	for i := 0; i <= len(sub); i++ {
		// 不变量：sub[0:start]中的regexp已被
		// 使用或标记为可重用，切片空间已被重用
		// 用于out（len（out）<=start）。
		// 
		// 不变量：sub[start:i]由所有以strflags修改的str开头的regexp组成。
		var istr []rune
		var iflags Flags
		if i < len(sub) {
			istr, iflags = p.leadingString(sub[i])
			if iflags == strflags {
				same := 0
				for same < len(str) && same < len(istr) && str[same] == istr[same] {
					same++
				}
				if same > 0 {
					// 匹配当前范围内至少一个符文。
					// 继续前进。
					str = str[:same]
					continue
				}
			}
		}

		// 找到了一个带有公共前导文字字符串的运行结束：
		// sub[start:i]都以str[0:len（str）]开头，但sub[i]
		// 甚至都不以str[0]开头。
		// 
		// 计算出公共字符串，并将计算出的表达式附加到out。
		if i == start {
			// 无事可做-长度为0的运行。
		} else if i == start+1 {
			// 只有一个：不用费心做保理。
			out = append(out, sub[start])
		} else {
			// 构造分解形式：前缀（后缀1 |后缀2 |……）
			prefix := p.newRegexp(OpLiteral)
			prefix.Flags = strflags
			prefix.Rune = append(prefix.Rune[:0], str...)

			for j := start; j < i; j++ {
				sub[j] = p.removeLeadingString(sub[j], len(str))
			}
			suffix := p.collapse(sub[start:i], OpAlternate) // 递归

			re := p.newRegexp(OpConcat)
			re.Sub = append(re.Sub[:0], prefix, suffix)
			out = append(out, re)
		}

		// 为下一次迭代做准备。
		start = i
		str = istr
		strflags = iflags
	}
	sub = out

	// 第二轮：去掉常见的简单前缀，
	// 只是每个串联的第一部分。
	// 很多时候这已经足够好了。
	// 
	// 复杂的子表达式（例如，涉及量词）
	// 是不安全的因素，因为这会折叠其通过自动机的不同路径，在某些情况下会影响
	// 正确性。
	start = 0
	out = sub[:0]
	var first *Regexp
	for i := 0; i <= len(sub); i++ {
		// 不变量：sub[0:start]中的regexp已被
		// 使用或标记为可重用，切片空间已被重用
		// 用于out（len（out）<=start）。
		// 
		// 不变量：sub[start:i]由所有以ifirst开头的regexp组成。
		var ifirst *Regexp
		if i < len(sub) {
			ifirst = p.leadingRegexp(sub[i])
			if first != nil && first.Equal(ifirst) &&
				// 首先必须是字符类或字符类的固定重复。
				(isCharClass(first) || (first.Op == OpRepeat && first.Min == first.Max && isCharClass(first.Sub[0]))) {
				continue
			}
		}

		// 找到了带有公共前导regexp的运行结束：
		// sub[start:i]都以first开头，但sub[i]不以first开头。
		// 
		// 将公共regexp因子输出，并将因子表达式附加到输出。
		if i == start {
			// 无事可做-运行长度为0。
		} else if i == start+1 {
			// 只有一个：不用费心做保理。
			out = append(out, sub[start])
		} else {
			// 构造分解形式：前缀（suffix1 | suffix2 |……）
			prefix := first
			for j := start; j < i; j++ {
				reuse := j != start // 前缀来自sub[start]
				sub[j] = p.removeLeadingRegexp(sub[j], reuse)
			}
			suffix := p.collapse(sub[start:i], OpAlternate) // 递归

			re := p.newRegexp(OpConcat)
			re.Sub = append(re.Sub[:0], prefix, suffix)
			out = append(out, re)
		}

		// 准备下一次迭代。
		start = i
		first = ifirst
	}
	sub = out

	// 第三轮：将单个文本的运行折叠为字符类。
	start = 0
	out = sub[:0]
	for i := 0; i <= len(sub); i++ {
		// 不变量：sub[0:start]中的regexp已被
		// 使用或标记为可重用，切片空间已被重用
		// 用于out（len（out）<=start）。
		// 
		// 不变量：sub[start:i]由两个或两个
		// 文字符文或字符类。
		if i < len(sub) && isCharClass(sub[i]) {
			continue
		}

		// sub[i]不是char或char类；
		// 为sub[start:i]发出字符类。。。
		if i == start {
			// 无事可做-运行长度为0。
		} else if i == start+1 {
			out = append(out, sub[start])
		} else {
			// 创建新的char类。
			// 以sub[Start]中最复杂的regexp开头。
			max := start
			for j := start + 1; j < i; j++ {
				if sub[max].Op < sub[j].Op || sub[max].Op == sub[j].Op && len(sub[max].Rune) < len(sub[j].Rune) {
					max = j
				}
			}
			sub[start], sub[max] = sub[max], sub[start]

			for j := start + 1; j < i; j++ {
				mergeCharClass(sub[start], sub[j])
				p.reuse(sub[j])
			}
			cleanAlt(sub[start])
			out = append(out, sub[start])
		}

		// /。。。然后发射sub[i]。
		if i < len(sub) {
			out = append(out, sub[i])
		}
		start = i + 1
	}
	sub = out

	// 第四轮：将空匹配的运行压缩为单个空匹配。
	start = 0
	out = sub[:0]
	for i := range sub {
		if i+1 < len(sub) && sub[i].Op == OpEmptyMatch && sub[i+1].Op == OpEmptyMatch {
			continue
		}
		out = append(out, sub[i])
	}
	sub = out

	return sub
}

// leadingString返回重新以开头的前导文本字符串。
// 该字符串表示re或其子项中的存储。
func (p *parser) leadingString(re *Regexp) ([]rune, Flags) {
	if re.Op == OpConcat && len(re.Sub) > 0 {
		re = re.Sub[0]
	}
	if re.Op != OpLiteral {
		return nil, 0
	}
	return re.Rune, re.Flags & FoldCase
}

// RemoveReadingString从re开头删除前n个前导符文
// 。它返回re的替换项。
func (p *parser) removeLeadingString(re *Regexp, n int) *Regexp {
	if re.Op == OpConcat && len(re.Sub) > 0 {
		// 删除串联中的前导字符串
		// 可能会简化串联。
		sub := re.Sub[0]
		sub = p.removeLeadingString(sub, n)
		re.Sub[0] = sub
		if sub.Op == OpEmptyMatch {
			p.reuse(sub)
			switch len(re.Sub) {
			case 0, 1:
				// 不可能，但要处理。
				re.Op = OpEmptyMatch
				re.Sub = nil
			case 2:
				old := re
				re = re.Sub[1]
				p.reuse(old)
			default:
				copy(re.Sub, re.Sub[1:])
				re.Sub = re.Sub[:len(re.Sub)-1]
			}
		}
		return re
	}

	if re.Op == OpLiteral {
		re.Rune = re.Rune[:copy(re.Rune, re.Rune[n:])]
		if len(re.Rune) == 0 {
			re.Op = OpEmptyMatch
		}
	}
	return re
}

// leadingRegexp返回重新开始的前导regexp。
// regexp指的是re或其子项中的存储。
func (p *parser) leadingRegexp(re *Regexp) *Regexp {
	if re.Op == OpEmptyMatch {
		return nil
	}
	if re.Op == OpConcat && len(re.Sub) > 0 {
		sub := re.Sub[0]
		if sub.Op == OpEmptyMatch {
			return nil
		}
		return sub
	}
	return re
}

// RemovelReadingRegExp删除re中的前导regexp。
// 它返回替换品以进行re。
// 如果reuse为true，则将删除的regexp（如果不再需要）传递给p.reuse。
func (p *parser) removeLeadingRegexp(re *Regexp, reuse bool) *Regexp {
	if re.Op == OpConcat && len(re.Sub) > 0 {
		if reuse {
			p.reuse(re.Sub[0])
		}
		re.Sub = re.Sub[:copy(re.Sub, re.Sub[1:])]
		switch len(re.Sub) {
		case 0:
			re.Op = OpEmptyMatch
			re.Sub = nil
		case 1:
			old := re
			re = re.Sub[0]
			p.reuse(old)
		}
		return re
	}
	if reuse {
		p.reuse(re)
	}
	return p.newRegexp(OpEmptyMatch)
}

func literalRegexp(s string, flags Flags) *Regexp {
	re := &Regexp{Op: OpLiteral}
	re.Flags = flags
	re.Rune = re.Rune0[:0] // 对小字符串使用本地存储
	for _, c := range s {
		if len(re.Rune) >= cap(re.Rune) {
			// 字符串太长，无法放入Rune0。让我们去处理吧。
			re.Rune = []rune(s)
			break
		}
		re.Rune = append(re.Rune, c)
	}
	return re
}


// Parse解析由指定的
// 标志控制的正则表达式字符串s，并返回正则表达式解析树。语法为
// 在顶级注释中描述。
func Parse(s string, flags Flags) (*Regexp, error) {
	return parse(s, flags)
}

func parse(s string, flags Flags) (_ *Regexp, err error) {
	defer func() {
		switch r := recover(); r {
		default:
			panic(r)
		case nil:
			// 好的
		case ErrInternalError:
			err = &Error{Code: ErrInternalError, Expr: s}
		}
	}()

	if flags&Literal != 0 {
		// 文本字符串的普通解析器。
		if err := checkUTF8(s); err != nil {
			return nil, err
		}
		return literalRegexp(s, flags), nil
	}

	// 否则，必须做真正的工作。
	var (
		p          parser
		c          rune
		op         Op
		lastRepeat string
	)
	p.flags = flags
	p.wholeRegexp = s
	t := s
	for t != "" {
		repeat := ""
	BigSwitch:
		switch t[0] {
		default:
			if c, t, err = nextRune(t); err != nil {
				return nil, err
			}
			p.literal(c)

		case '(':
			if p.flags&PerlX != 0 && len(t) >= 2 && t[1] == '?' {
				// 标志更改和非捕获组。
				if t, err = p.parsePerlFlags(t); err != nil {
					return nil, err
				}
				break
			}
			p.numCap++
			p.op(opLeftParen).Cap = p.numCap
			t = t[1:]
		case '|':
			if err = p.parseVerticalBar(); err != nil {
				return nil, err
			}
			t = t[1:]
		case ')':
			if err = p.parseRightParen(); err != nil {
				return nil, err
			}
			t = t[1:]
		case '^':
			if p.flags&OneLine != 0 {
				p.op(OpBeginText)
			} else {
				p.op(OpBeginLine)
			}
			t = t[1:]
		case '$':
			if p.flags&OneLine != 0 {
				p.op(OpEndText).Flags |= WasDollar
			} else {
				p.op(OpEndLine)
			}
			t = t[1:]
		case '.':
			if p.flags&DotNL != 0 {
				p.op(OpAnyChar)
			} else {
				p.op(OpAnyCharNotNL)
			}
			t = t[1:]
		case '[':
			if t, err = p.parseClass(t); err != nil {
				return nil, err
			}
		case '*', '+', '?':
			before := t
			switch t[0] {
			case '*':
				op = OpStar
			case '+':
				op = OpPlus
			case '?':
				op = OpQuest
			}
			after := t[1:]
			if after, err = p.repeat(op, 0, 0, before, after, lastRepeat); err != nil {
				return nil, err
			}
			repeat = before
			t = after
		case '{':
			op = OpRepeat
			before := t
			min, max, after, ok := p.parseRepeat(t)
			if !ok {
				// 如果无法分析重复，则{是一个文字。
				p.literal('{')
				t = t[1:]
				break
			}
			if min < 0 || min > 1000 || max > 1000 || max >= 0 && min > max {
				// 数字太大，或者存在max，并且min>max。
				return nil, &Error{ErrInvalidRepeatSize, before[:len(before)-len(after)]}
			}
			if after, err = p.repeat(op, min, max, before, after, lastRepeat); err != nil {
				return nil, err
			}
			repeat = before
			t = after
		case '\\':
			if p.flags&PerlX != 0 && len(t) >= 2 {
				switch t[1] {
				case 'A':
					p.op(OpBeginText)
					t = t[2:]
					break BigSwitch
				case 'b':
					p.op(OpWordBoundary)
					t = t[2:]
					break BigSwitch
				case 'B':
					p.op(OpNoWordBoundary)
					t = t[2:]
					break BigSwitch
				case 'C':
					// 任何字节；不支持
					return nil, &Error{ErrInvalidEscape, t[:2]}
				case 'Q':
					// /\Q…\E:…始终是文字
					var lit string
					lit, t, _ = strings.Cut(t[2:], `\E`)
					for lit != "" {
						c, rest, err := nextRune(lit)
						if err != nil {
							return nil, err
						}
						p.literal(c)
						lit = rest
					}
					break BigSwitch
				case 'z':
					p.op(OpEndText)
					t = t[2:]
					break BigSwitch
				}
			}

			re := p.newRegexp(OpCharClass)
			re.Flags = p.flags

			// 查找Unicode字符组，如\p{Han 
			if len(t) >= 2 && (t[1] == 'p' || t[1] == 'P') {
				r, rest, err := p.parseUnicodeClass(t, re.Rune0[:0])
				if err != nil {
					return nil, err
				}
				if r != nil {
					re.Rune = r
					t = rest
					p.push(re)
					break BigSwitch
				}
			}

			// Perl字符类转义。
			if r, rest := p.parsePerlClassEscape(t, re.Rune0[:0]); r != nil {
				re.Rune = r
				t = rest
				p.push(re)
				break BigSwitch
			}
			p.reuse(re)

			// 普通单字符转义。
			if c, t, err = p.parseEscape(t); err != nil {
				return nil, err
			}
			p.literal(c)
		}
		lastRepeat = repeat
	}

	p.concat()
	if p.swapVerticalBar() {
		// 弹出垂直条
		p.stack = p.stack[:len(p.stack)-1]
	}
	p.alternate()

	n := len(p.stack)
	if n != 1 {
		return nil, &Error{ErrMissingParen, s}
	}
	return p.stack[0], nil
}

// parseRepeat解析{min}（max=min）或{min，}（max=-1）或{min，max}。
// 如果s不是那种形式，则返回ok==false。
// 如果s的形式正确，但值太大，则返回min=-1，ok==true。
func (p *parser) parseRepeat(s string) (min, max int, rest string, ok bool) {
	if s == "" || s[0] != '{' {
		return
	}
	s = s[1:]
	var ok1 bool
	if min, s, ok1 = p.parseInt(s); !ok1 {
		return
	}
	if s == "" {
		return
	}
	if s[0] != ',' {
		max = min
	} else {
		s = s[1:]
		if s == "" {
			return
		}
		if s[0] == '}' {
			max = -1
		} else if max, s, ok1 = p.parseInt(s); !ok1 {
			return
		} else if max < 0 {
			// parseInt发现太大的数字
			min = -1
		}
	}
	if s == "" || s[0] != '}' {
		return
	}
	rest = s[1:]
	ok = true
	return
}

// parsePerlFlags解析Perl标志设置或非捕获组或两者，
// like（？i）或（？：或（？i:.）它从s中删除前缀并更新解析状态。
// 调用者必须确保s以“（？”开头。
func (p *parser) parsePerlFlags(s string) (rest string, err error) {
	t := s

	// 检查命名捕获，它首先在Python的regexp库中引入。
	// 像往常一样，有三种稍有不同的语法：
	// 
	// /（？P<name>expr）原始语法，由Python 
	// /（？<name>expr）引入。NET修改，由Perl 5.10 
	// /（？“name”expr）另一个采用。NET修改，被Perl 5.10 
	// 
	// Perl 5.10采用并实现了Python版本，
	// 但他们声称后两种是首选形式。
	// PCRE和基于PCRE的语言（特别是PHP和Ruby）
	// 也支持这三种语言。EcmaScript 4只使用Python形式。
	// 
	// 在开源世界（通过代码搜索）和
	// 谷歌源代码树中，（？P<expr>name）是主要形式，
	// 所以这就是我们实现的。一个就够了。
	if len(t) > 4 && t[2] == 'P' && t[3] == '<' {
		// 拔出名称。
		end := strings.IndexRune(t, '>')
		if end < 0 {
			if err = checkUTF8(t); err != nil {
				return "", err
			}
			return "", &Error{ErrInvalidNamedCapture, s}
		}

		capture := t[:end+1] // ”（P<name>“
		name := t[4:end]     // ”name“
		if err = checkUTF8(name); err != nil {
			return "", err
		}
		if !isValidCaptureName(name) {
			return "", &Error{ErrInvalidNamedCapture, capture}
		}

		// 与普通捕获类似，但命名为。
		p.numCap++
		re := p.op(opLeftParen)
		re.Cap = p.numCap
		re.Name = name
		return t[end+1:], nil
	}

	// 非捕获组。可能还会旋转Perl标志。
	var c rune
	t = t[2:] // 跳过（？
	flags := p.flags
	sign := +1
	sawFlag := false
Loop:
	for t != "" {
		if c, t, err = nextRune(t); err != nil {
			return "", err
		}
		switch c {
		default:
			break Loop

		// 标志。
		case 'i':
			flags |= FoldCase
			sawFlag = true
		case 'm':
			flags &^= OneLine
			sawFlag = true
		case 's':
			flags |= DotNL
			sawFlag = true
		case 'U':
			flags |= NonGreedy
			sawFlag = true

		// 切换为否定。
		case '-':
			if sign < 0 {
				break Loop
			}
			sign = -1
			// 反转标志，使上面的|变成&^，反之亦然。
			// 我们将在下面使用它之前再次反转标志。
			flags = ^flags
			sawFlag = false

		// 结束标志，开始组或不开始组。
		case ':', ')':
			if sign < 0 {
				if !sawFlag {
					break Loop
				}
				flags = ^flags
			}
			if c == ':' {
				// 打开新组
				p.op(opLeftParen)
			}
			p.flags = flags
			return t, nil
		}
	}

	return "", &Error{ErrInvalidPerlOp, s[:len(s)-len(t)]}
}

// isValidCaptureName报告是否命名
// 是一个有效的捕获名称：[a-Za-z0-9\]+。
// PCRE将名称限制为32字节。
// Python拒绝以数字开头的名称。
// 这两项我们都不执行。
func isValidCaptureName(name string) bool {
	if name == "" {
		return false
	}
	for _, c := range name {
		if c != '_' && !isalnum(c) {
			return false
		}
	}
	return true
}

// parseInt解析十进制整数。
func (p *parser) parseInt(s string) (n int, rest string, ok bool) {
	if s == "" || s[0] < '0' || '9' < s[0] {
		return
	}
	// 不允许前导零。
	if len(s) >= 2 && s[0] == '0' && '0' <= s[1] && s[1] <= '9' {
		return
	}
	t := s
	for s != "" && '0' <= s[0] && s[0] <= '9' {
		s = s[1:]
	}
	rest = s
	ok = true
	// 有数字，计算值。
	t = t[:len(t)-len(s)]
	for i := 0; i < len(t); i++ {
		// 避免溢出。
		if n >= 1e8 {
			n = -1
			break
		}
		n = n*10 + int(t[i]) - '0'
	}
	return
}

// 这可以表示为字符类吗？
// 单个符文文本字符串，char类。，还有|\n、 
func isCharClass(re *Regexp) bool {
	return re.Op == OpLiteral && len(re.Rune) == 1 ||
		re.Op == OpCharClass ||
		re.Op == OpAnyCharNotNL ||
		re.Op == OpAnyChar
}

// 重新匹配r吗？
func matchRune(re *Regexp, r rune) bool {
	switch re.Op {
	case OpLiteral:
		return len(re.Rune) == 1 && re.Rune[0] == r
	case OpCharClass:
		for i := 0; i < len(re.Rune); i += 2 {
			if re.Rune[i] <= r && r <= re.Rune[i+1] {
				return true
			}
		}
		return false
	case OpAnyCharNotNL:
		return r != '\n'
	case OpAnyChar:
		return true
	}
	return false
}

// parseVerticalBar处理输入中的|。
func (p *parser) parseVerticalBar() error {
	p.concat()

	// 我们刚刚解析的连接位于堆栈顶部。
	// 如果它位于opVerticalBar上方，则在
	// （opVerticalBar下方的内容将成为可选内容）下方交换。
	// 否则，按一个新的竖条。
	if !p.swapVerticalBar() {
		p.op(opVerticalBar)
	}

	return nil
}

// mergeCharClass使dst=dst | src。
// 调用方必须确保dst。Op>=src。Op，
// 减少复制量。
func mergeCharClass(dst, src *Regexp) {
	switch dst.Op {
	case OpAnyChar:
		// src没有添加任何内容。
	case OpAnyCharNotNL:
		// src可能会添加\n 
		if matchRune(src, '\n') {
			dst.Op = OpAnyChar
		}
	case OpCharClass:
		// src更简单，因此literal或char类
		if src.Op == OpLiteral {
			dst.Rune = appendLiteral(dst.Rune, src.Rune[0], src.Flags)
		} else {
			dst.Rune = appendClass(dst.Rune, src.Rune)
		}
	case OpLiteral:
		// literal 
		if src.Rune[0] == dst.Rune[0] && src.Flags == dst.Flags {
			break
		}
		dst.Op = OpCharClass
		dst.Rune = appendLiteral(dst.Rune[:0], dst.Rune[0], dst.Flags)
		dst.Rune = appendLiteral(dst.Rune, src.Rune[0], src.Flags)
	}
}

// 。
// 否则返回false。
func (p *parser) swapVerticalBar() bool {
	// 如果竖条上下是文字或字符类，
	// 可以合并为单个字符类。
	n := len(p.stack)
	if n >= 3 && p.stack[n-2].Op == opVerticalBar && isCharClass(p.stack[n-1]) && isCharClass(p.stack[n-3]) {
		re1 := p.stack[n-1]
		re3 := p.stack[n-3]
		// 让re3成为两者中更复杂的一个。
		if re1.Op > re3.Op {
			re1, re3 = re3, re1
			p.stack[n-3] = re3
		}
		mergeCharClass(re3, re1)
		p.reuse(re1)
		p.stack = p.stack[:n-1]
		return true
	}

	if n >= 2 {
		re1 := p.stack[n-1]
		re2 := p.stack[n-2]
		if re2.Op == opVerticalBar {
			if n >= 3 {
				// 现在已经够不着了。
				// 机会主义地清理。
				cleanAlt(p.stack[n-3])
			}
			p.stack[n-2] = re1
			p.stack[n-1] = re2
			return true
		}
	}
	return false
}

// parseRightParen在输入中处理a）。
func (p *parser) parseRightParen() error {
	p.concat()
	if p.swapVerticalBar() {
		// 弹出垂直条
		p.stack = p.stack[:len(p.stack)-1]
	}
	p.alternate()

	n := len(p.stack)
	if n < 2 {
		return &Error{ErrUnexpectedParen, p.wholeRegexp}
	}
	re1 := p.stack[n-1]
	re2 := p.stack[n-2]
	p.stack = p.stack[:n-2]
	if re2.Op != opLeftParen {
		return &Error{ErrUnexpectedParen, p.wholeRegexp}
	}
	// 在paren时恢复标志。
	p.flags = re2.Flags
	if re2.Cap == 0 {
		// 仅用于分组。
		p.push(re1)
	} else {
		re2.Op = OpCapture
		re2.Sub = re2.Sub0[:1]
		re2.Sub[0] = re1
		p.push(re2)
	}
	return nil
}

// parseEscape解析s开头的转义序列
// 并返回符文。
func (p *parser) parseEscape(s string) (r rune, rest string, err error) {
	t := s[1:]
	if t == "" {
		return 0, "", &Error{ErrTrailingBackslash, ""}
	}
	c, t, err := nextRune(t)
	if err != nil {
		return 0, "", err
	}

Switch:
	switch c {
	default:
		if c < utf8.RuneSelf && !isalnum(c) {
			// 转义的非单词字符总是自己。PCRE并没有那么严格：它接受像
			// /\q这样的东西，但我们不接受。我们曾经拒绝过\，但太多的
			// 程序和人们坚持使用它，所以允许\。
			return c, t, nil
		}

	// 八进制逃逸。
	case '1', '2', '3', '4', '5', '6', '7':
		// 单个非零数字为反向参考；不支持
		if t == "" || t[0] < '0' || t[0] > '7' {
			break
		}
		fallthrough
	case '0':
		// 最多使用三个八进制数字；已经有了。
		r = c - '0'
		for i := 1; i < 3; i++ {
			if t == "" || t[0] < '0' || t[0] > '7' {
				break
			}
			r = r*8 + rune(t[0]) - '0'
			t = t[1:]
		}
		return r, t, nil

	// 十六进制转义。
	case 'x':
		if t == "" {
			break
		}
		if c, t, err = nextRune(t); err != nil {
			return 0, "", err
		}
		if c == '{' {
			// 大括号中的任意位数。
			// Perl完全接受任何文本；它忽略第一个非十六进制数字后的所有文本
			// 。我们只需要十六进制数字
			// 和至少一个。
			nhex := 0
			r = 0
			for {
				if t == "" {
					break Switch
				}
				if c, t, err = nextRune(t); err != nil {
					return 0, "", err
				}
				if c == '}' {
					break
				}
				v := unhex(c)
				if v < 0 {
					break Switch
				}
				r = r*16 + v
				if r > unicode.MaxRune {
					break Switch
				}
				nhex++
			}
			if nhex == 0 {
				break Switch
			}
			return r, t, nil
		}

		// 简单的大小写：两个十六进制数字。
		x := unhex(c)
		if c, t, err = nextRune(t); err != nil {
			return 0, "", err
		}
		y := unhex(c)
		if x < 0 || y < 0 {
			break
		}
		return x*16 + y, t, nil

	// C逃脱。在POSIX模式下，不存在“b”的情况，以避免将
	// Perl单词边界\b误放为C backspace\b 
	// 的情况。在Perl中，/\b/表示单词边界
	// 但/[\b]/表示退格。我们不支持这一点。
	// 如果需要退格，请嵌入文字退格
	// 字符或使用\x08。
	case 'a':
		return '\a', t, err
	case 'f':
		return '\f', t, err
	case 'n':
		return '\n', t, err
	case 'r':
		return '\r', t, err
	case 't':
		return '\t', t, err
	case 'v':
		return '\v', t, err
	}
	return 0, "", &Error{ErrInvalidEscape, s[:len(s)-len(t)]}
}

// parseClassChar解析s开头的字符类字符
// 并返回它。
func (p *parser) parseClassChar(s, wholeClass string) (r rune, rest string, err error) {
	if s == "" {
		return 0, "", &Error{Code: ErrMissingBracket, Expr: wholeClass}
	}

	// 允许常规转义序列，即使
	// 在这种情况下，许多不需要转义。
	if s[0] == '\\' {
		return p.parseEscape(s)
	}

	return nextRune(s)
}

type charGroup struct {
	sign  int
	class []rune
}

// parsePerlClassEscape从s开头解析一个领先的Perl字符类转义，如\d 
// 如果有，它会将字符附加到r 
// 并返回新的片段r和字符串的其余部分。
func (p *parser) parsePerlClassEscape(s string, r []rune) (out []rune, rest string) {
	if p.flags&PerlX == 0 || len(s) < 2 || s[0] != '\\' {
		return
	}
	g := perlGroup[s[0:2]]
	if g.sign == 0 {
		return
	}
	return p.appendGroup(r, g), s[2:]
}

// parseNamedClass从s开头解析一个领先的POSIX命名字符类，如[:alnum:]
// 如果存在，则将字符追加到r 
// 并返回新的片段r和字符串的其余部分。
func (p *parser) parseNamedClass(s string, r []rune) (out []rune, rest string, err error) {
	if len(s) < 2 || s[0] != '[' || s[1] != ':' {
		return
	}

	i := strings.Index(s[2:], ":]")
	if i < 0 {
		return
	}
	i += 2
	name, s := s[0:i+2], s[i+2:]
	g := posixGroup[name]
	if g.sign == 0 {
		return nil, "", &Error{ErrInvalidCharRange, name}
	}
	return p.appendGroup(r, g), s, nil
}

func (p *parser) appendGroup(r []rune, g charGroup) []rune {
	if p.flags&FoldCase == 0 {
		if g.sign < 0 {
			r = appendNegatedClass(r, g.class)
		} else {
			r = appendClass(r, g.class)
		}
	} else {
		tmp := p.tmpClass[:0]
		tmp = appendFoldedClass(tmp, g.class)
		p.tmpClass = tmp
		tmp = cleanClass(&p.tmpClass)
		if g.sign < 0 {
			r = appendNegatedClass(r, tmp)
		} else {
			r = appendClass(r, tmp)
		}
	}
	return r
}

var anyTable = &unicode.RangeTable{
	R16: []unicode.Range16{{Lo: 0, Hi: 1<<16 - 1, Stride: 1}},
	R32: []unicode.Range32{{Lo: 1 << 16, Hi: unicode.MaxRune, Stride: 1}},
}

// unicodeTable返回unicode。由名称
// 标识的范围表和附加折叠等效代码点表。
func unicodeTable(name string) (*unicode.RangeTable, *unicode.RangeTable) {
	// 特殊情况：“任何”指任何。
	if name == "Any" {
		return anyTable, anyTable
	}
	if t := unicode.Categories[name]; t != nil {
		return t, unicode.FoldCategory[name]
	}
	if t := unicode.Scripts[name]; t != nil {
		return t, unicode.FoldScript[name]
	}
	return nil, nil
}

// ParseUnicode类从s开头解析一个领先的Unicode字符类，如\p{Han}
// 如果存在，则将字符附加到r 
// 并返回新的片段r和字符串的其余部分。
func (p *parser) parseUnicodeClass(s string, r []rune) (out []rune, rest string, err error) {
	if p.flags&UnicodeGroups == 0 || len(s) < 2 || s[0] != '\\' || s[1] != 'p' && s[1] != 'P' {
		return
	}

	// 已提交解析或返回错误。
	sign := +1
	if s[1] == 'P' {
		sign = -1
	}
	t := s[2:]
	c, t, err := nextRune(t)
	if err != nil {
		return
	}
	var seq, name string
	if c != '{' {
		// 单字母名称。
		seq = s[:len(s)-len(t)]
		name = seq[2:]
	} else {
		// 名称用大括号括起来。
		end := strings.IndexRune(s, '}')
		if end < 0 {
			if err = checkUTF8(s); err != nil {
				return
			}
			return nil, "", &Error{ErrInvalidCharRange, s}
		}
		seq, t = s[:end+1], s[end+1:]
		name = s[3:end]
		if err = checkUTF8(name); err != nil {
			return
		}
	}

	// 组也可以有前导否定。\p{^Han}==\p{Han}，p{^Han}==\p{Han}。
	if name != "" && name[0] == '^' {
		sign = -sign
		name = name[1:]
	}

	tab, fold := unicodeTable(name)
	if tab == nil {
		return nil, "", &Error{ErrInvalidCharRange, seq}
	}

	if p.flags&FoldCase == 0 || fold == nil {
		if sign > 0 {
			r = appendTable(r, tab)
		} else {
			r = appendNegatedTable(r, tab)
		}
	} else {
		// 合并并清洁标签，并在临时缓冲区中折叠。
		// 这对于阴性病例是必要的，而对于阳性病例则是必要的。
		tmp := p.tmpClass[:0]
		tmp = appendTable(tmp, tab)
		tmp = appendTable(tmp, fold)
		p.tmpClass = tmp
		tmp = cleanClass(&p.tmpClass)
		if sign > 0 {
			r = appendClass(r, tmp)
		} else {
			r = appendNegatedClass(r, tmp)
		}
	}
	return r, t, nil
}

// parseClass解析s 
// 开头的字符类，并将其推送到解析堆栈上。
func (p *parser) parseClass(s string) (rest string, err error) {
	t := s[1:] // chop[
	re := p.newRegexp(OpCharClass)
	re.Flags = p.flags
	re.Rune = re.Rune0[:0]

	sign := +1
	if t != "" && t[0] == '^' {
		sign = -1
		t = t[1:]

		// 如果字符类不匹配，请将其添加到此处，
		// 这样以后否定就会做正确的事情。
		if p.flags&ClassNL == 0 {
			re.Rune = append(re.Rune, '\n', '\n')
		}
	}

	class := re.Rune
	first := true // ]和-可以作为类中的第一个字符
	for t == "" || t[0] != ']' || first {
		// POSIX:-可以作为类中的第一个或最后一个字符。
		// Perl:-在任何地方都可以。
		if t != "" && t[0] == '-' && p.flags&PerlX == 0 && !first && (len(t) == 1 || t[1] != ']') {
			_, size := utf8.DecodeRuneInString(t[1:])
			return "", &Error{Code: ErrInvalidCharRange, Expr: t[:1+size]}
		}
		first = false

		// 查找POSIX[：alnum：]等。
		if len(t) > 2 && t[0] == '[' && t[1] == ':' {
			nclass, nt, err := p.parseNamedClass(t, class)
			if err != nil {
				return "", err
			}
			if nclass != nil {
				class, t = nclass, nt
				continue
			}
		}

		// 查找Unicode字符组，如\p{Han}。
		nclass, nt, err := p.parseUnicodeClass(t, class)
		if err != nil {
			return "", err
		}
		if nclass != nil {
			class, t = nclass, nt
			continue
		}

		// 查找Perl字符类符号（扩展名）。
		if nclass, nt := p.parsePerlClassEscape(t, class); nclass != nil {
			class, t = nclass, nt
			continue
		}

		// 单个字符或简单范围。
		rng := t
		var lo, hi rune
		if lo, t, err = p.parseClassChar(t, s); err != nil {
			return "", err
		}
		hi = lo
		// /[a-]表示（a |-）所以请检查最终结果]。
		if len(t) >= 2 && t[0] == '-' && t[1] != ']' {
			t = t[1:]
			if hi, t, err = p.parseClassChar(t, s); err != nil {
				return "", err
			}
			if hi < lo {
				rng = rng[:len(rng)-len(t)]
				return "", &Error{Code: ErrInvalidCharRange, Expr: rng}
			}
		}
		if p.flags&FoldCase == 0 {
			class = appendRange(class, lo, hi)
		} else {
			class = appendFoldedRange(class, lo, hi)
		}
	}
	t = t[1:] // 印章]

	// 使用和重新使用。符文而不是&class以避免分配。
	re.Rune = class
	class = cleanClass(&re.Rune)
	if sign < 0 {
		class = negateClass(class)
	}
	re.Rune = class
	p.push(re)
	return t, nil
}

// cleanClass对范围（r的元素对）进行排序，
// 合并它们，并消除重复项。
func cleanClass(rp *[]rune) []rune {

	// 按lo递增、hi递减排序，以打破联系。
	sort.Sort(ranges{rp})

	r := *rp
	if len(r) < 2 {
		return r
	}

	// 合并邻接，重叠。
	w := 2 // 写入索引
	for i := 2; i < len(r); i += 2 {
		lo, hi := r[i], r[i+1]
		if lo <= r[w-1]+1 {
			// 与上一个范围合并
			if hi > r[w-1] {
				r[w-1] = hi
			}
			continue
		}
		// 新的不相交范围
		r[w] = lo
		r[w+1] = hi
		w += 2
	}

	return r[:w]
}

// appendLiteral返回将文本x附加到类r的结果。
func appendLiteral(r []rune, x rune, flags Flags) []rune {
	if flags&FoldCase != 0 {
		return appendFoldedRange(r, x, x)
	}
	return appendRange(r, x, x)
}

// appendRange返回将范围低高附加到类r的结果。
func appendRange(r []rune, lo, hi rune) []rune {
	// 如果重叠，则扩展上一个范围或下一个范围或邻接。
	// 在附加大小写折叠字母表时，检查两个范围会有所帮助，这样一个范围可以扩展A-Z，另一个范围可以扩展A-Z。
	n := len(r)
	for i := 2; i <= 4; i += 2 { // 两次，使用i=2，i=4 
		if n >= i {
			rlo, rhi := r[n-i], r[n-i+1]
			if lo <= rhi+1 && rlo <= hi+1 {
				if lo < rlo {
					r[n-i] = lo
				}
				if hi > rhi {
					r[n-i+1] = hi
				}
				return r
			}
		}
	}

	return append(r, lo, hi)
}

const (
	// 折叠中涉及的最小和最大符文。
	// 在测试期间检查。
	minFold = 0x0041
	maxFold = 0x1e943
)

// AppendFolderRange返回将范围lo hi 
// 及其大小写折叠等效符文追加到类r的结果。
func appendFoldedRange(r []rune, lo, hi rune) []rune {
	// 优化。
	if lo <= minFold && hi >= maxFold {
		// 范围已满：折叠无法添加更多内容。
		return appendRange(r, lo, hi)
	}
	if hi < minFold || lo > maxFold {
		// 范围超出折叠范围。
		return appendRange(r, lo, hi)
	}
	if lo < minFold {
		// /[lo，minFold-1]不需要折叠。
		r = appendRange(r, lo, minFold-1)
		lo = minFold
	}
	if hi > maxFold {
		// /[maxFold+1，hi]无需折叠。
		r = appendRange(r, maxFold+1, hi)
		hi = maxFold
	}

	// 蛮力。依靠appendRange来实时合并范围。
	for c := lo; c <= hi; c++ {
		r = appendRange(r, c, c)
		f := unicode.SimpleFold(c)
		for f != c {
			r = appendRange(r, f, f)
			f = unicode.SimpleFold(f)
		}
	}
	return r
}

// appendClass返回将类x附加到类r的结果。
// 它假定x是干净的。
func appendClass(r []rune, x []rune) []rune {
	for i := 0; i < len(x); i += 2 {
		r = appendRange(r, x[i], x[i+1])
	}
	return r
}

// AppendFolderd返回将类x的大小写折叠附加到类r的结果。
func appendFoldedClass(r []rune, x []rune) []rune {
	for i := 0; i < len(x); i += 2 {
		r = appendFoldedRange(r, x[i], x[i+1])
	}
	return r
}

// appendNegatedClass返回将类x的否定附加到类r的结果。
// 它假定x是干净的。
func appendNegatedClass(r []rune, x []rune) []rune {
	nextLo := '\u0000'
	for i := 0; i < len(x); i += 2 {
		lo, hi := x[i], x[i+1]
		if nextLo <= lo-1 {
			r = appendRange(r, nextLo, lo-1)
		}
		nextLo = hi + 1
	}
	if nextLo <= unicode.MaxRune {
		r = appendRange(r, nextLo, unicode.MaxRune)
	}
	return r
}

// appendTable返回将x附加到类r的结果。
func appendTable(r []rune, x *unicode.RangeTable) []rune {
	for _, xr := range x.R16 {
		lo, hi, stride := rune(xr.Lo), rune(xr.Hi), rune(xr.Stride)
		if stride == 1 {
			r = appendRange(r, lo, hi)
			continue
		}
		for c := lo; c <= hi; c += stride {
			r = appendRange(r, c, c)
		}
	}
	for _, xr := range x.R32 {
		lo, hi, stride := rune(xr.Lo), rune(xr.Hi), rune(xr.Stride)
		if stride == 1 {
			r = appendRange(r, lo, hi)
			continue
		}
		for c := lo; c <= hi; c += stride {
			r = appendRange(r, c, c)
		}
	}
	return r
}

// appendNegatedTable返回将x的求反附加到类r的结果。
func appendNegatedTable(r []rune, x *unicode.RangeTable) []rune {
	nextLo := '\u0000' // lo结束下一个类以添加
	for _, xr := range x.R16 {
		lo, hi, stride := rune(xr.Lo), rune(xr.Hi), rune(xr.Stride)
		if stride == 1 {
			if nextLo <= lo-1 {
				r = appendRange(r, nextLo, lo-1)
			}
			nextLo = hi + 1
			continue
		}
		for c := lo; c <= hi; c += stride {
			if nextLo <= c-1 {
				r = appendRange(r, nextLo, c-1)
			}
			nextLo = c + 1
		}
	}
	for _, xr := range x.R32 {
		lo, hi, stride := rune(xr.Lo), rune(xr.Hi), rune(xr.Stride)
		if stride == 1 {
			if nextLo <= lo-1 {
				r = appendRange(r, nextLo, lo-1)
			}
			nextLo = hi + 1
			continue
		}
		for c := lo; c <= hi; c += stride {
			if nextLo <= c-1 {
				r = appendRange(r, nextLo, c-1)
			}
			nextLo = c + 1
		}
	}
	if nextLo <= unicode.MaxRune {
		r = appendRange(r, nextLo, unicode.MaxRune)
	}
	return r
}

// negateClass覆盖r并返回r的求反。
// 它假定类r已经是干净的。
func negateClass(r []rune) []rune {
	nextLo := '\u0000' // 在下一个类的末尾添加
	w := 0             // 写入索引
	for i := 0; i < len(r); i += 2 {
		lo, hi := r[i], r[i+1]
		if nextLo <= lo-1 {
			r[w] = nextLo
			r[w+1] = lo - 1
			w += 2
		}
		nextLo = hi + 1
	}
	r = r[:w]
	if nextLo <= unicode.MaxRune {
		// 否定可能比原始类多一个
		// 范围-这一个，所以使用append。
		r = append(r, nextLo, unicode.MaxRune)
	}
	return r
}

// 排序。[]符文上的接口。
// 接收器类型定义的选择很奇怪
// 但是避免了分配，因为我们已经有了
// a*[]符文。
type ranges struct {
	p *[]rune
}

func (ra ranges) Less(i, j int) bool {
	p := *ra.p
	i *= 2
	j *= 2
	return p[i] < p[j] || p[i] == p[j] && p[i+1] > p[j+1]
}

func (ra ranges) Len() int {
	return len(*ra.p) / 2
}

func (ra ranges) Swap(i, j int) {
	p := *ra.p
	i *= 2
	j *= 2
	p[i], p[i+1], p[j], p[j+1] = p[j], p[j+1], p[i], p[i+1]
}

func checkUTF8(s string) error {
	for s != "" {
		rune, size := utf8.DecodeRuneInString(s)
		if rune == utf8.RuneError && size == 1 {
			return &Error{Code: ErrInvalidUTF8, Expr: s}
		}
		s = s[size:]
	}
	return nil
}

func nextRune(s string) (c rune, t string, err error) {
	c, size := utf8.DecodeRuneInString(s)
	if c == utf8.RuneError && size == 1 {
		return 0, "", &Error{Code: ErrInvalidUTF8, Expr: s}
	}
	return c, s[size:], nil
}

func isalnum(c rune) bool {
	return '0' <= c && c <= '9' || 'A' <= c && c <= 'Z' || 'a' <= c && c <= 'z'
}

func unhex(c rune) rune {
	if '0' <= c && c <= '9' {
		return c - '0'
	}
	if 'a' <= c && c <= 'f' {
		return c - 'a' + 10
	}
	if 'A' <= c && c <= 'F' {
		return c - 'A' + 10
	}
	return -1
}
